The present invention relates to a method of scheduling and more particularly to a method of scheduling tasks which employs a genetic algorithm for progressively improving possible solutions to a scheduling problem.
As is understood by those skilled in the art, scheduling and planning are difficult problems which do not easily yield to automated solving. They are problems which are typically tackled with a combination of search techniques and heuristics. Scheduling is difficult for various reasons. It is a computationally complex problem described in computer science terms as NP complete. This means that search techniques that deterministically and exhaustively search the space of possibilities will probably fail because of time requirements. On the other hand, search techniques that use heuristics to prune the search space will not be guaranteed to find an optimal solution or even a good one. Further, scheduling problems are often complicated by the details of a particular scheduling task. Algorithmic consideration of the specific constraints must often be embodied in what amounts to a domain specific expert system. Thus, any given such system has limited applicability. How the expert knowledge is embedded into an optimization algorithm is often very algorithm specific.
It has previously been proposed to apply genetic algorithms to scheduling problems. As is understood by those skilled in the art, genetic algorithms function by applying operators, e.g. crossover and mutation, to a population of possible solutions often referred to in the art as "chromosomes". Traditionally, chromosomes are simple binary vectors. This simple representation has substantial appeal and the theoretical grounding of genetic algorithms is based on the binary vectors and simple operators. However, many problems emerge when one attempts to represent complicated problems using binary vectors. The success of genetic algorithms in finding good solutions is in general rather directly a function of the manner in which the chromosomes are encoded to represent possible solutions. The situation is further complicated in scheduling problems in that the usual methods of applying crossover and mutation may generate illegal solutions and the genetic algorithm will then in effect spend substantial effort in exploring unhelpful search space. Encoding methods attempting to avoid these problems are described in Davis, L. (1985). Job shop scheduling with genetic algorithms. Proceedings of an International Conference on Genetic Algorithms and Their Applications. Hillsdale, N.J.: Lawrence Erlbaum Associates. and Whitley, D., T. Starkweather, and D. Fuquay (1989). Scheduling problems and the traveling salesman: the genetic edge recombination operator. Proceedings of the Third International Conference on Genetic Algorithms and Their Applications. San Mateo, Calif.: Morgan Kaufmann.
Among the several objects of the present invention may be noted the provision of a novel method for creating schedules; the provision of such a method which will effectively schedule tasks, each of which requires selected resources from a predetermined pool of resources for respective time intervals; the provision of such a method which will schedule tasks having associated therewith various constraints, some of which may be hard or rigid and others of which may be more in the nature of preferences; the provision of such a method which will consistently generate good solutions to complex scheduling problems; the provision of such a method which is easily adaptable to a variety of scheduling problems; the provision of such a method which is adapted to automated or computerized implementation; the provision of such a method which operates quickly; and the provision of such a method which is highly reliable and which may be implemented relatively inexpensively. Other objects and features will be in part apparent and in part pointed out hereinafter.
In accordance with the practice of the present invention, a genetic algorithm is employed which utilizes chromosomes which are not simple binary vectors but, rather, are more indirect representations of possible solutions, for example, merely ordered lists of tasks to be performed. Further, the genetic algorithm is insulated from domain specific knowledge by the inclusion, in the overall system, of a deterministic schedule builder. The schedule builder operates to place the tasks in a given list into a legal schedule, i.e. a schedule which complies with the various hard constraints which may be associated with each task. Legal schedules generated in this manner are then evaluated or scored on the basis of the various soft or preferential constraints to determine how good the putative schedule is. The scores of possible solutions are provided as feedback to the genetic algorithm for use in controlling the operators which effect evolution of the population of solutions.
In a preferred embodiment, the method of the present invention operates to schedule tasks, each of which requires selected resources from a predetermined pool of resources for respective time intervals, each task having associated constraints and an associated scoring function for evaluating its inclusion within a schedule. An initial population of sequential task lists is generated, preferably randomly. The successive tasks in each list are sequentially fit into a respective legal schedule, observing the associated constraints. Each possible schedule in the population is evaluated in accordance with the scoring function to obtain a ranking of the respective lists. Pairs of higher ranking lists are stochastically selected for combination to generate new member lists to be added to the population and lower ranked lists are stochastically deleted from the population. Preferably, mutation is periodically applied by stochastically selecting a pair of tasks in one of the task lists and reversing the positions of the pair in that list.